\documentstyle[12pt]{report⎇   % adjust the pt size
% Adjustment of margins.
\topmargin -.5in
\textheight 8.6in
\oddsidemargin .5in
\textwidth 6in
\renewcommand{\topfraction⎇{.99⎇
\renewcommand{\bottomfraction⎇{.99⎇
\renewcommand{\textfraction⎇{.01⎇ 
%\renewcommand{\baselinestretch⎇{2.0⎇	% Double spacing for editors
% \textwidth 4.25in	      % Correct for two-column pasteup.
\newcommand{\comment⎇[1]{⎇
\renewcommand{\thesection⎇{\arabic{section⎇⎇
\renewcommand{\thesubsection⎇{\Alph{subsection⎇⎇
\renewcommand\descriptionlabel[1]{\bf #1. \hfil⎇
\renewcommand\thebibliography[1]
	      {\subsubsection{References⎇
	       \vskip -\bigskipamount
\list{[\arabic{enumi⎇]⎇{\settowidth\labelwidth{[#1]⎇\leftmargin\labelwidth
\advance\leftmargin\labelsep\usecounter{enumi⎇⎇⎇
\def\bottomfraction{.7⎇
\setlength{\unitlength⎇{1mm⎇
\begin{document⎇
\renewcommand{\thefigure⎇{\arabic{figure⎇⎇
\setcounter{figure⎇{0⎇
\title{LOGIC AND ARTIFICIAL INTELLIGENCE⎇
\author{Nils J. Nilsson \\
\\
Computer Science Department \\
Stanford University \\
Stanford, CA 94305 \\
\  \\
\  \\
DRAFT OF ARTICLE TO APPEAR IN THE BOOK \\
FOUNDATIONS OF ARTIFICIAL INTELLIGENCE \\
From the MIT June 1987 Workshop \\
\  \\
COMMENTS TO NILSSON@SCORE.STANFORD.EDU ⎇

\maketitle

\section{Introduction⎇

Until a technological endeavor achieves a substantial number of its
goals it is wise for it to pursure several competing approaches.  So it
is with Artificial Intelligence (AI).  AI researchers have programmed a
number of demonstration systems that exhibit a fair degree of
intelligence in limited domains (and some systems that even have
commercial potential).  However, we are still far from achieving the
versatile cognitive skills of humans.  And so research continues along a
number of paths---each with its ardent proponents.  Although successful
AI systems of the future will probably draw on a combination of
techniques, it is useful to study the different approaches in their pure
forms in order to highlight strengths and weaknesses.  Here, I present
my view of the ``logical approach'' to AI.

Since those pursuing the logical approach differ about its aims and
methods, it is not surprising that the approach is not understood very
well by many ``non-logical'' AI researchers.  Some of the criticisms of
the use of logic in AI stem from confusion about what its practitioners
claim for it.  In describing logic and AI, we first relate the logical
approach to a number of theses that one might make about the role of
knowledge in intelligent systems.  Then we examine the theoretical
foundations underlying the logical approach.  Next, we consider some
important observations gained from experience with the approach.
Lastly, we confront some limitations of logic and describe what is being
done in an attempt to overcome them.  For a textbook-length treatment of
logic and AI see \cite{Genesereth1987⎇.

\section{Artificial Intelligence and \protect\\Declarative Knowledge⎇

We begin with a series of theses:

\begin{quote⎇
{\it 
1.  Intelligent machines will have knowledge of their environments.⎇
\end{quote⎇
Perhaps this statement is non-controversial.  It is probably definitional.

\begin{quote⎇
{\it 2.  The most versatile machines will have {\rm declarative⎇ knowledge.⎇
\end{quote⎇
AI researchers have long argued the merits of declarative as opposed to
procedural knowledge.  Roughly speaking, we mean by declarative
knowledge that knowledge encoded in the machine in the form of sentences
in some language, and we mean by procedural knowledge that knowledge
manifested in programs.  When knowledge is represented as declarative
sentences, the sentences are manipulated by reasoning processes when the
machine is deciding what to do.  The first serious proposal for an
intelligent system with declarative knowledge
was by John McCarthy in 1958
\cite{McCarthy1958⎇.  McCarthy noted the versatility of declaratively
represented knowledge: it could be used by the machine even for purposes
unforeseen by the machine's designer, it could more easily be modified
than could knowledge embodied in programs, and it facilitated
communication between the machine and other machines and humans.  As he
said later ``Sentences can be true in much wider contexts than specific
programs can be useful'' \cite{McCarthy1987⎇.

Many database systems and expert systems can be said to use declarative
knowledge.  The ``frames'' and ``semantic networks'' used by several AI
programs can be regarded as sets of declarative sentences.  Indeed,
some expert systems that do not use declarative knowledge have been
criticized for their lack of versatility.  

It should be pointed out that some researchers who are not persuaded
about the power of the logical approach to AI nevertheless acknowledge
the importance of declarative knowledge.  In another chapter of this
volume Lenat and Feigenbaum state: ``The knowledge in INTERNIST [needed
for coupling to a machine learning program, for example] isn't stored in
the right way, ...''  \cite{Lenat1988⎇.  (INTERNIST \cite{Pople⎇ is a
program for assisting physicians in making medical diagnoses.  Although
its knowledge is represented as data structures, these data structures
are not easily interpreted as sentences in a language.)

There are several examples of successful AI systems that do not
represent knowledge about the world as declarative sentences.  Many of
these are described in the other chapters of this book.

\begin{quote⎇ 
{\it 3.  The language in which declarative knowledge is
represented must be at least as expressive as first-order predicate
calculus.⎇
\end{quote⎇
One might hope that a natural language such as English might serve as
the language in which to represent knowledge for intelligent systems.
If this were possible, then all of the knowledge already compiled in
books would be immediately available for use by computers.  Although
humans somehow understand English well enough, it is too ambiguous a
representational medium for computers---the meaning of English sentences
depends too much on the contexts in which they are uttered and
understood.

AI researchers have experimented with a wide variety of languages in
which to represent sentences.  Some of these languages have limited
expressive power.  They might not have a means for saying that one or
another of two facts is true without saying which fact is true.  Some
cannot say that a fact is not true without saying what is true instead.
They might not be able to say that {\it all⎇ the members of a class have
a certain property without explicitly listing each of them.  Finally,
some are not able to state that at least one member of a class has a
certain property without stating which member does.  First-order
predicate calculus, through its ability to formulate disjunctions,
negations, and universally and existentially quantified sentences, does
not suffer from these limitations.

The logical approach to AI usually involves a commitment to all of these
theses.

\section{Foundations of the Logical Approach⎇

\begin{quote⎇
{\it Through naming comes knowing; we grasp an object, mentally, by giving it
a name---hension, prehension, apprehension.  And thus through language
create a whole world, corresponding to the other world out there.  Or we
trust that it corresponds.  Or perhaps, like a German poet, we cease to
care, becoming more concerned with the naming than with the things
named; the former becomes more real than the later.  And so in the end
the world is lost again.  No, the world remains---those unique,
particular, incorrigibly individual junipers and sandstone
monoliths---and it is we who are lost.  Again.  Round and round, through
the endless labyrinth of thought---the maze. ---Edward
Abbey⎇\footnote{From {\it Desert Solitaire⎇, p. 288-289, Ballantine Books,
New York, 1971.⎇ 
\end{quote⎇

The logical approach to AI involves more than just expressing a machine's
knowledge as sentences in the predicate calculus.  It also embodies a
point of view about what knowledge is, what the world is, how a machine
interacts with the world, and the role and extent of special procedures
in the design of intelligent machines.

Those designers who would claim that their machines possess
``knowledge'' about the world are obliged to say something about what
that claim means.  The fact that a machine's knowledge base has an
expression in it like ${\tt (\forall x) Box(x) \supset Green(x)⎇$, for
example, doesn't by itself justify the claim that the machine {\it
believes⎇ all boxes are green.  (The mnemonic relation constants that
we use in our design aren't mnemonic for the machine!  We could
just as well have written ${\tt (\forall x) G011(x) \supset G023(x)⎇$.)

There are different views of what it means for a machine possessing a
database of sentences to believe the facts intended by those sentences.
The view that I favor involves making some (perhaps unusual)
metaphysical assumptions about what we take the ``real world'' to be and
about how our machines interact with that world.  I will give a
simplified account of this view here.  It is based, in part, on a
discussion of intelligent agent architecture in \cite[Chapter
13]{Genesereth1987⎇.

Figure}\ref{fig1⎇ shows a machine interacting with the world.  Both
machine and world are regarded as finite-state machines.  We denote the
machine state by ${\bf M⎇$; it is one of a set ${\cal M⎇$ of states.  We
denote the world state by ${\bf W⎇$; it is one of a set ${\cal W⎇$ of
states.  The input to the machine is denoted by ${\bf S⎇$---one of a set
${\cal S⎇$ of inputs; the output of the machine is denoted by ${\bf
A⎇$---one of a set ${\cal A⎇$ of outputs.  States, inputs, and outputs
are related as follows: the function {\it see⎇ maps ${\cal W⎇$ into
${\cal S⎇$; the function {\it mem⎇ maps ${\cal S⎇ \times {\cal M⎇$ into
${\cal M⎇$; the function {\it act⎇ maps ${\cal S⎇ \times {\cal M⎇$ into
${\cal A⎇$; lastly, the function {\it effect⎇ maps ${\cal A⎇ \times
{\cal W⎇$ into ${\cal W⎇$.  The function {\it see⎇ models the fact that
the machine is not sensitive to every aspect of the world; it partitions
the world into classes whose members, as far as the machine is
concerned, are equivalent.  The function {\it mem⎇ models the machine's
memory behavior; the machine's state at any instant is a function of the
machine's input and its previous state.  The function {\it act⎇
describes how the machine acts on the world; its action is a function of
its state and its input.  We model the effects of these actions on the
world (as well as the world's own internal dynamics) by {\it effect⎇.

\begin{figure⎇
\begin{center⎇
 \begin{picture⎇(100,24)
 \put(25,12){\oval(24,24)⎇
 \put(25,15){\makebox(0,0){Machine⎇⎇%
 \put(25,9){\makebox(0,0){{\bf M⎇⎇⎇%
\put(50,19){\makebox(0,0){{\bf S⎇⎇⎇%
\put(50,5){\makebox(0,0){{\bf A⎇⎇⎇%
 \put(75,12){\oval(24,24)⎇
 \put(75,15){\makebox(0,0){World⎇⎇%
 \put(75,9){\makebox(0,0){{\bf W⎇⎇⎇%
 \put(37,8){\vector(1,0){26⎇⎇
 \put(63,16){\vector(-1,0){26⎇⎇
 \end{picture⎇
\end{center⎇
 \caption{Machine and World⎇
 \label{fig1⎇
\end{figure⎇

Our story about what the world ``really is'' involves additional
articulation.  We imagine that it is a mathematical structure consisting
of {\it objects⎇, {\it functions⎇, and {\it relations⎇.  That is, each
world state is labeled by a set of objects, functions, and
relations.  The function {\it effect⎇ produces a new world state by
changing one or more of these objects, functions, or 
relations.  Furthermore, the function {\it see⎇ is a function of the 
objects, functions, and relations.  So, in this view, the
world is taken (actually!) to be a mathematical structure that undergoes
changes---partly in response to the machine's output and partly as a
result of its own dynamics; and which produces signals impinging on the
machine.

Now, the designer of a machine that must interact with the world never
knows what the world objects, functions, and relations actually are.
Neither does he know {\it see⎇ nor {\it effect⎇.  He must guess.
Guessing involves invention on the designer's part.  (Our machine
designer is in the same predicament as is the scientist; scientists {\it
invent⎇ descriptions of the world and gradually refine them until they
suit society's purposes.)  We use the term {\it conceptualization⎇ to
describe the designer's guess about the world objects, functions, and
relations, and about {\it see⎇ and {\it effect⎇.  The designer may not
even be able to specify a single conceptualization; for example he may
choose not to commit himself regarding whether an object he invents, say
a block, has the color property Green or Blue.  Thus, in general, the
designer attempts to specify a set of conceptualizations such that,
whatever the world is, he guesses it is a member of the set.

The designer realizes, of course, that his conceptualization might not
accurately capture the world.  But he tries to invent a
conceptualization that is {\it good enough⎇, considering the purposes of
the machine.  When it becomes apparent that the conceptualization is
deficient (and that this deficiency is the cause of inadequate machine
performance), then the designer can modify his conceptualization.

We stress that the objects guessed to exist in the world by the designer
are {\it invented⎇.  He is perfectly free to invent anything that makes
the machine perform appropriately, and he doesn't ask whether or not some
object {\it really⎇ does or does not exist (whatever that might mean).
For many ordinary, concrete objects such as chairs, houses, people, and
so on, we can be reasonably confident that our inventions mirror
reality.  But some of the things that we might want to include as world
objects, such as {\it precambrian unconformities⎇, English sentences,
{\it the Peloponnesian War⎇, $\pi$, and {\it truth⎇, have a somewhat
more arbitrary ontological status.  In fact, much of the designer's
guess about the world may be quite arbitrary in the sense that other
guesses would have suited his purposes equally well.  (Even those
following other declarative, but putatively non-logical, approaches must
invent the equivalent of objects, relations, and functions when they attempt
to give their machines declarative knowledge.)

A {\it logicist⎇ (as those following the logical approach are sometimes
called) expresses his conceptualization of the world in sentences and by
the function {\it mem⎇.  We focus on the sentences first.  We assume
that the sentences are in the first-order predicate calculus; this
language and the sentences in it are constructed as follows: For every
world object in the conceptualization, we create an {\it object
constant⎇; for every world relation, we create a {\it relation
constant⎇; and for every world function, we create a {\it function
constant⎇.  Using these constructs, and the syntax of predicate
calculus, we (the designer) then compose a set of sentences to express
knowledge we are willing to assume about the world.

When a designer cannot specify which of two relations holds, he uses a
disjunction, such as: ${\tt Box(Ob1) \wedge [Blue(Ob1) \vee
Green(Ob1)]⎇$.  Or he may use an existentially quantified statement:
${\tt (\exists x)Box(x) \wedge Green(x)⎇$.  Or, he might know that all
boxes are green: ${\tt (\forall x) Box(x) \supset Green(x)⎇$.

In what sense can we say that a collection of predicate calculus
sentences represents {\it knowledge⎇ about the world?  Our answer to this
question involves the notions of {\it interpretations⎇ and {\it models⎇
of sentences in the predicate calculus.  Briefly, an interpretation
consists of: 
\begin{enumerate⎇ 
\item an assignment of a relation to each
relation constant 
\item an assignment of an object to each object
constant 
\item an assignment of a function to each function constant
\item a procedure for assigning the values $T$ (true) or $F$ (false) to each
closed formula. (This procedure involves {\it evaluating⎇ ground atomic
formulas using the relation/object/function assignments and then using
the standard logical truth tables for non-atomic ground sentences.  The
description of how quantified sentences are evaluated is slightly more
complex but respects the intuitive meanings of the quantifiers.)
\end{enumerate⎇
Any interpretation for which all of the sentences in a set of sentences
evaluates to {\it T⎇ is called a {\it model⎇ of the set of sentences.

In terms of these definitions, the designer's task can be viewed as follows:
\begin{quote⎇
Invent world objects, relations, and functions and a first-order predicate
calculus language and a set of sentences in that language such that the
interpretation of those sentences (using the world objects, functions, and
relations) is a model of the set of sentences.
\end{quote⎇

We will call the world objects, relations, and functions invented by the
designer, the {\it intended model⎇ of the sentences the designer uses to
describe the world.  Although this interpretation itself may never
actually be represented explicitly as mathematical structure, it is
important that it be firmly fixed in the mind of the designer.  With
this interpretation in mind, the designer invents linguistic terms to
denote his invented objects, functions, and relations and writes down
predicate calculus sentences for which the intended interpretation is a
model.

The designer gives the machine knowledge about the world by storing
these sentences in the machine's memory.  We call the set of sentences
the {\it knowledge base⎇ of the machine and denote the set by $\Delta$.
That is, each ${\bf M⎇←i$ in ${\cal M⎇$ is labeled by a
$\Delta←i$.

Additional knowledge is represented in {\it mem⎇.  The function {\it
mem⎇ changes the sentences---one hopes in a manner that mirrors the way
{\it effect⎇ changes the objects, relations, and functions which are the
world and in a manner that is sensitive to what the machine senses
through {\bf S⎇.  Perhaps new sentences are added or existing ones are
modified or deleted.  The function {\it mem⎇ may also produce a state
change in the absence of new sensory information; changes to $\Delta$
may occur through processes of deduction or other types of inference
as will be described below.

Even when the designer has a single intended interpretation in mind,
$\Delta$, in general, will be satisfied by a set of
interpretations---the intended one among them.  The designer must
provide sufficient sentences in the knowledge base such that its models
are limited---limited so that even though the set has more than one
model, it doesn't matter for the purposes of the machine.  (To the
extent that it {\it does⎇ matter, the designer must then provide more
sentences.)  In designing knowledge bases, it frequently happens that
the designer's idea of the intended interpretation is changed and
articulated by the very act of writing down (and reasoning with) the
sentences.

So, a machine possessing a set of sentences {\it knows⎇ about the world
in the sense that these sentences admit of a set of models, and this set
is the designer's best guess about what the world actually is.  The actual
world might not even be in the set (the designer's guess might be wrong),
so we really should be talking about the machine's {\it beliefs⎇ rather
than the machine's {\it knowledge⎇; but we will continue to use the
term knowledge because that is what, after all, we aspire to.

The machine's knowledge affects its actions through the function {\it act⎇.
We take {\it act⎇ to be a function over sets of sentences that produces
actions.  Note that {\it act⎇ can thus only respond to sentences  {\it qua
sentences⎇, that is, as strings of symbols.  It is not a function of the
models of these sentences!

Given this picture, we can identify a spectrum of design choices.  At one end,
{\it act⎇ and {\it mem⎇ are highly specialized to the tasks the machine
is expected to perform and to the environment in which it operates.  We
might say, in this case, that the machine's knowledge is largely {\it
procedural⎇.  At the other extreme, {\it act⎇ and {\it mem⎇ are general
purpose and largely independent of the application.  All
application-specific knowledge is represented in $\Delta$.  The
machine's knowledge in this case can be said to be largely {\it
declarative⎇.  The logical approach usually involves a commitment to
represent most of the machine's knowledge declaratively.  For a proposal
at the extreme declarative end, see Genesereth and Nilsson \cite[Chapter
13]{Genesereth1987⎇.  It is not yet known to what extent this goal can
be achieved while maintaining reasonable efficiency.

Because the actions emitted by {\it act⎇ depend on the syntactic form of
the sentences in $\Delta$, it is necessary for {\it mem⎇ to be able to
rewrite these sentences in the form appropriate to the task at hand.
This aspect of {\it mem⎇ we call {\it reasoning⎇.  Imagine, for example,
a robot designed to paint boxes green.  Its sentence-to-action process,
{\it act⎇, may include a {\it production rule⎇ like ``If $\Delta$
includes the sentence ${\tt Box(\eta)⎇$ for some value of $\eta$, paint
the object denoted by ${\tt \eta⎇$ green.''  But suppose $\Delta$
includes the sentences ${\tt (\forall x)Blue(x) \supset Box(x)⎇$ and
${\tt Blue(G17)⎇$ but not ${\tt Box(G17)⎇$.  We might expect that
correct behavior for this robot would be to paint the object denoted by
${\tt G17⎇$ green, but there is no sentence-to-action rule to accomplish
that.  The sentence ${\tt Box(G17)⎇$ must appear in $\Delta$ before
appropriate action can occur.  Constructing the sentence ${\tt
Box(G17)⎇$ from the sentences ${\tt (\forall x)Blue(x) \supset Box(x)⎇$
and ${\tt Blue(G17)⎇$ is an example of one kind of sentence
manipulation, or {\it inference⎇, that we want {\it mem⎇ to do.

Often, as in the box-painting example, the new sentence constructed from
ones already in memory does not tell us anything new about the world.
(All of the models of ${\tt (\forall x)Blue(x) \supset Box(x)⎇$ and ${\tt
Blue(G17)⎇$ are also models of ${\tt Box(G17)⎇$. Thus, adding
${\tt Box(G17)⎇$ to $\Delta$ does not reduce the set of models.)
What the new sentence tells us was already implicitly said by the
sentences from which it was constructed.  

If all of the models of $\Delta$ are also models of a sentence $\phi$,
we say that $\Delta$ {\it logically entails⎇ $\phi$ and write
$\Delta \models \phi$. Among the computations that we might want {\it mem⎇
to perform are those which add sentences to $\Delta$ that are logically
entailed by $\Delta$.  One apparent problem in devising such
computations is the prospect of having to check {\it all⎇ the models of
$\Delta$ to see if they are also models of $\phi$.  But, fortunately,
there exist strictly syntactic operations on $\Delta$ that are able to
compute logically entailed formulas.

We use the phrase {\it rule of inference⎇ to refer to any computation on
a set of sentences that produces a new sentence.  If $\psi$ can be
derived from $\Delta$ by a sequence of applications of rules of
inference, we say that $\psi$ can be {\it deduced⎇ from $\Delta$ and
write $\Delta \vdash \psi$.  An example is the rule of inference called
{\it modus ponens⎇.  From any sentences of the form $\rho \supset
\sigma$ and $\rho$, we can deduce the sentence $\sigma$ by modus ponens.
The process of logical deduction involves using a set of rules of
inference to deduce additional sentences from a set of sentences.
Interestingly, it happens that there are rules of inference, modus
ponens is an example, that have the property that if $\Delta \vdash
\phi$, then $\Delta \models \phi$.  Such rules of inference are called
{\it sound⎇.

Sound rules of inference are extremely important because they allow us
to compute sentences that are logically entailed by a set of sentences
using computations on the sentences themselves (and not on their models).

We can also find inference rules that have the property that if $\Delta
\models \phi$ then the rules (successively applied) will eventually
produce such a $\phi$.  Such a set of inference rules is called {\it
complete⎇.

Although all logicists typically incorporate sound inference rules as
part of the calculations performed by {\it mem⎇, there is no necessary
reason to limit {\it mem⎇ to performing sound inferences.  Other
computations are often desirable. We will describe some of these later
in the chapter.

\section{Comments on the Logical Approach⎇

The basic idea underlying the logical approach to AI is simple, but 
attempts to use it have resulted in several additional important
insights.

\subsection{The Importance of Conceptualization⎇

The most important part of ``the AI problem'' involves inventing an
appropriate conceptualization (intended model).  It is not easy for a
designer to squeeze his intuitive and commonsense ideas about the world
into a coherent conceptualization involving objects, functions, and
relations.  Although this exercise has been carried out for several
limited problem domains (most notably those to which expert systems have
been successfully applied), there are some particularly difficult
subjects to conceptualize.  Among these are liquids and other ``mass
substances,'' processes, events, actions, beliefs, time, goals,
intentions, and plans.  Some researchers feel that the {\it frame
problem⎇, for example, arises as it does as an artifact of an
inappropriate (state-based) conceptualization of change
\cite{Hayes1979⎇.  Others feel that change must involve the notion of
time (instead of the notion of state) \cite{Shoham1987⎇.
Conceptualizing the ``cognitive state'' of intelligent agents has been
the subject of recent intense study.  (See, for example,
\cite{Cohen1987⎇ for a treatment of the intentions of agents and
\cite{Moore1985⎇ and \cite{Konolige1985⎇ for treatments of the
knowledge and beliefs of agents.) Interestingly, many of the most
difficult conceptualization problems arise when attempting to express
knowledge about the everyday, ``commonsense'' world (see
\cite{Hobbs1985a⎇ and \cite{Hobbs1985b⎇).  AI researchers join company
with philosophers who have also been attempting to formalize some of
these ideas.

Choosing to use first-order predicate calculus as a representation
language does not relieve us of the chore of deciding {\it what⎇ to say
in that language.  Deciding what to say is harder than designing the
language in which to say it!  The logical approach to AI carries with it
no special insights into what conceptualizations to use.  (Logic is
often criticized for providing {\it form⎇ but not {\it content⎇.  Of
course!)

It is important to stress that these conceptualization problems do not
arise simply as an undesireable side effect of the use of logic.  They
must be confronted and resolved by any approach that attempts to
represent knowledge of the world by sentence-like, declarative
structures.

\subsection{Sound and Unsound Inferences⎇

Another important observation concerns the subject of sound inference.
Logicists are sometimes criticized for their alleged dependence on
deduction.  Much human thought, the critics rightly claim, involves
leaps of intuition, inductive inference, and other guessing strategies
that lie outside the realm of sound inference.  There are two things
that can be said about such criticism.  

First, logicists regard sound inference as an important, but not the
only, component of reasoning.  We must be careful to note the
circumstances under which both sound and unsound inferences might
appropriately be used.  Recall that the set of sentences $\Delta$ (with
which a designer endows a machine) implicitly defines a set of models.
Either the designer actually has some subset of these models in mind (as
his guess about what the world is) or he is completely uncertain about
which of the models might represent the world.  If he really is
uncertain, nothing other than sound inference would be desired by the
designer.  Any deduced sentence $\phi$ had better be logically entailed
by $\Delta$; if there are some models of $\Delta$, for example, that are
not models of $\phi$, and if the designer wanted the machine to conclude
$\phi$, then he wouldn't have been completely uncertain about which of
the models of $\Delta$ represented the world.

If the designer had some subset of the models of $\Delta$ in mind, and
if (for one reason or another) he could not specify this subset by
enlarging $\Delta$, then there are circumstances under which unsound
inference might be appropriate.  For example, the designer may have some
preference function over the models of $\Delta$.  He may want to focus,
for example, on the minimal models (according to the preference
function).  These minimal models may be better guesses, in the
designer's mind, about the real world than would be the other models of
$\Delta$. In that case, the inference $\phi$ would be appropriate if all
the minimal models of $\Delta$ were models of $\phi$.

McCarthy \cite{McCarthy1980⎇ and Lifschitz \cite{Lifschitz1985⎇ have
studied a variety of such preference functions over models and have
investigated an (unsound) inference computation, called {\it
circumscription⎇, that is based on them.  Several aspects of commonsense
reasoning, including induction and default inferences, appear to require
something like circumscription.

Another example of unsound inference is {\it inductive inference⎇.  For
example, from the premises ${\tt Emerald(Ob1) \wedge Color(Ob1,
Green)⎇$, ${\tt Emerald(Ob2) \wedge Color(Ob2, Green)⎇$, $\ldots$, ${\tt
Emerald(Obn) \wedge Color(Obn, Green)⎇$, we may want to inductively infer
(unsoundly but reasonably) ${\tt (\forall x)Emerald(x) \supset
Color(x, Green)⎇$ if there is no $\eta$ mentioned in $\Delta$ such that
$\Delta$ entails ${\tt Emerald(\eta) \wedge \neg Color(\eta, Green)⎇$.  

The second thing that can be said about sound inference is that, in the
context of sufficient additional information, conclusions can be drawn
that might have seemed to have required unsound inference.  For example,
suppose $\Delta$ contains the following statements: \[{\tt (\exists y)
(\forall x)Emerald(x) \supset Color(x,y)⎇\] (Intended meaning: There is
a color such that all emeralds have that color.)  \[{\tt (\forall
x,y,z)[Color(x,y) \wedge Color(x,z)] \supset (y=z)⎇\] (Intended meaning:
A thing can have only one color.)  

From these statements, we can deduce
that if a thing is an emerald, it has a unique color.  Now, if we
subsequently learn \[{\tt Color(Ob1, Green) \wedge Emerald(Ob1)⎇\] we
can deduce (soundly) ${\tt (\forall x)Emerald(x) \supset
Color(x,Green)⎇$.  $\Delta$ already told us that all emeralds have the
same unique color, but did not specify what that color was.  Later
information added to $\Delta$ allowed us to deduce a more specific
general rule.

\subsection{Semantic Attachment to Partial Models⎇

Earlier, we mentioned that it was fortunate that sound inference
techniques existed because it would be impossible in most situations to
check that all the models of $\Delta$ were also models of some formula
$\phi$.  In some cases, however, it is possible to perform calculations
on model-like structures.  Often, calculations on models are much more
efficient than are inference processes, and we would be well advised to
include them as part of a machine's reasoning apparatus.

We mentioned that seldom does a designer make explicit his guess about
the world, the intended model.  The set of models is implicitly defined
by the set of sentences in $\Delta$.  Sometimes, however, it is possible
to be explicit about at least part of the intended model.  That is, we
might be able to construct a part of the model as list structure and
programs in, say, LISP.  For example, we can represent objects as LISP
atoms, functions as LISP functions, and relations as LISP predicates.
In such cases we can perform reasoning by computations with these LISP
constructs that we might otherwise have performed by logical inference
on the predicate calculus sentences.  This point has previously been
made by a number of researchers---most notably by Weyhrauch
\cite{Weyhrauch1980⎇.  Typically, the LISP constructs will be a {\it
partial⎇ model; that is there might not be LISP referents for all of the
expressions in the predicate calculus sentences, and/or the LISP
functions and predicates themselves may be defined over just a subset of
the intended domain.  (In the following we will not always be careful
about saying {\it partial⎇ models and interpretations even though those
are what we really mean.)

As an example, consider the predicate calculus sentences: 
\[{\tt P(A)⎇\]
\[{\tt (\forall x)P(x) \supset Q(x)⎇\] 
Presumably these sentences stem from a certain conceptualization of the
world.  Suppose we can capture this conceptualization in LISP.  Our
intended interpretation for ${\tt P⎇$ is (represented by) a certain LISP
predicate {\bf P⎇; our intended interpretation for ${\tt Q⎇$ is a
certain LISP predicate {\bf Q⎇; and our intended interpretation for
${\tt A⎇$ is a certain LISP atom {\bf A⎇.  If these intended (partial)
interpretations are to be parts of models for $\Delta$, then we know
that {\bf (P A)⎇ and {\bf (OR (NOT (P A)) (Q A))⎇ will both evaluate to
{\bf T⎇.  Thus, we must make sure that {\bf (Q A)⎇ evalutes to {\bf T⎇.

So, this gives us two ways to compute the truth value of ${\tt Q(A)⎇$
with respect to the intended model.  Given the initial sentences, we
could deduce ${\tt Q(A)⎇$ using sound inference rules.  That is, if a
reasoning program needed to know whether or not ${\tt Q(A)⎇$ was true,
it could find that it is true using logical inference.  The fact that
${\tt Q(A)⎇$ can be (soundly) deduced from the other sentences means
that ${\tt Q(A)⎇$ is logically entailed by them.  And that means that
{\it all⎇ of the models of the initial sentences are also models of
${\tt Q(A)⎇$.  That means, {\it a fortiori⎇, that the {\it intended⎇
model of the initial sentence (whatever it is) is a model of ${\tt
Q(A)⎇$.

The other way to compute the truth value of ${\tt Q(A)⎇$ is to associate
${\tt Q(A)⎇$ with {\bf (Q A)⎇ and evaluate {\bf (Q A)⎇ in LISP.  We call
this association {\it semantic attachment⎇.  Semantic attachment to
appropriate computational structures, when such are available, is
usually more efficient than inference.  It provides a means for
determining the truth of an expression directly in the intended model
rather than by establishing its truth in all models indirectly by sound
inference.

Several standard structures and programs are already commonly used in
reasoning systems.  For example, tree structures are useful for
representing taxonomic hierarchies (in fact some knowledge
representation languages use such tree-structure representations
explicitly as part of the language \cite{Brachman1985⎇).  Various LISP
ordering predicates combined with appropriate directed-graph data
structures are useful for representing transitive binary relations.  It
is my guess that efficient reasoning systems will probably rely very
heavily on semantic attachment using these and other common constructs.
Logical entailment (through its computational stand-in---sound logical
deduction) will be used mainly as a powerful ``fall-back'' method for
reasoning.  Because the latter guarantees that a derived sentence is
satisfied by a whole set of interpretations (including the intended
one), it may be too strong for most purposes---and thus too expensive.
All that we really need is to know whether the {\it intended⎇ interpretation
is a model of the sentence in question.

\subsection{Reification of Theories⎇

Sometimes we will want our machines to reason about the sentences in its
knowledge base.  We may, for example, want them to reason about the
lengths of sentences or about their complexity.  Our conceptualizations
will thus have to acknowledge that things called sentences exist in the
world.  Conferring {\it existence⎇ on abstract concepts (such as
sentences) is often called {\it reification⎇.

We might reify whole theories.  This will allow us to say, for example,
that some $\Delta←1$ is more appropriate than is some $\Delta←2$ when
confronted with problems of diagnosing bacterial infections.  Scientists
are used to having different---even contradictory---theories to explain
reality: quantum physics, Newtonian mechanics, relativity, wave theories
of light, particle theories of light, and so on.  Each is useful in
certain circumstances.  Although scientists search for a uniform,
all-embracing, and consistent picture of reality, historically they have
had to settle for a collection of somewhat different theories.  There is
nothing in the logicist approach that forces us to have just {\it one⎇
conceptualization of the world.  There is no reason to think AI would be
any more successful at that goal than scientists have been!

When theories are reified, {\it metatheory⎇ (that is, a theory about
theories) can be used to make decisions about which local theory should
be used in which circumstances.  The metatheory will contain statements,
also expressed in predicate calculus, about such matters.  Metatheory can
also provide information to guide the inference procedures operating
over local theories.  For example, we might want to say that when two
inferences are possible in some $\Delta←1$, the inference that results
in the most general conclusion should be preferred.  Using metatheory
to express knowledge about how to control inference is consistent with
the logicists' desire to put as much knowledge as possible in
declarative form (as opposed to ``building it in'' to the functions
{\it mem⎇ and {\it act⎇).

Weyhrauch \cite{Weyhrauch1980⎇ has pointed out that the process of
semantic attachment in a metatheory can be particularly powerful.
Commonly, even when no semantic attachments are possible to speed
reasoning in a theory, the problem at hand can be dispatched efficiently
by appropriate semantic attachment in the metatheory.

Some critics of the logical approach have claimed that since {\it
anything⎇ can be said in the metatheory, its use would seem to be a
retreat to the same ad hoc tricks used by less disciplined AI
researchers.  But we think there are generally useful things to say in
the metatheory that are not themselves problem dependent.  That is, we
think that knowledge about how to use knowledge can itself be expressed
as context-free, declarative sentences.  (Lenat's work has uncovered the
best examples of generally useful statements about how to use knowledge
\cite{Lenat1982,Lenat1983a,Lenat1983b⎇.)

\subsection{Other Observations⎇

Even though logicists frequently call the sentences in their knowledge
bases {\it axioms⎇, they are not necessarily committed to represent
knowledge by a minimal set of sentences.  Indeed, some (or even most) of
the sentences in $\Delta$ may be derivable from others. Since the
``intelligence'' of an agent depends on how much usable declarative
knowledge it has, we agree completely with those who say ``In the
knowledge lies the power.'' We do not advocate systems that rely on
search-based derivations of knowledge when it is possible to include the
needed knowledge directly in the knowledge base.

The occasional criticism that logicists depend too heavily on their
inference methods and not on the knowledge base must simply result from
a misunderstanding of the goals of the logical approach.  As has already
been pointed out, logicists strive to make the inference process as
uniform and domain independent as possible and to represent all
knowledge (even the knowledge about how to use knowledge) declaratively.

Some critics have claimed that the logical approach is not efficient
enough to handle ``real-world'' problems.  It is true that knowledge can
be brought to bear on a problem more efficiently when its use is
tailored to the special features of that problem.  Efficient knowledge
use does depend on the situation.  When knowledge is encoded in a
fashion that permits many different uses, several possible ways in which
to use it may have to be tried, and the resulting search process takes
time.  A price does have to be paid for generality.

Much progress has been made, however, in making inference processes more
efficient.  Stickel has developed one of the most powerful
first-order-logic theorem provers \cite{Stickel1982,Stickel1984⎇.
Several resolution refutation systems have been written that are able to
solve large, nontrivial reasoning problems, including some open problems
in mathematics \cite{Winker1982,Wos1984⎇.  Many large-scale AI systems
depend heavily on predicate calculus representations and reasoning
methods.  Among the more substantial of these are TEAM, a natural
language interface to databases \cite{Grosz1987⎇; DART, a program for
equipment design and repair \cite{Genesereth1984⎇; and KAMP, a program
that generates English sentences \cite{Appelt1985⎇.

Also, as previously mentioned, the efficiency of reasoning systems can
often be greatly enhanced by semantic attachment to partial models.

\section{Challenges⎇

\subsection{Language and the World⎇

Few would argue that intelligent machines must have some kind of
characterization or model of the world they inhabit.  We have stressed
that the main feature of machines designed using the logical approach is
that they describe their worlds by {\it language⎇.  Is language (any
language) adequate to the task?  As the writer Edward
Abbey\footnote{From {\it Desert Solitaire⎇, p. {\it x⎇, Ballantine
Books, New York, 1971.⎇ observes: \begin{quote⎇ {\it Language makes a pretty
loose net with which to go fishing for simple facts, when facts are
infinite.⎇  \end{quote⎇

A designer's intuitive ideas about what the world is are often difficult
to capture in a conceptualization that can be described by a finite set
of sentences.  Usually these intuitive ideas are never complete at the
time of design anyway, and the conceptualization expands making it
difficult for the sentences to catch up.

John McCarthy humorously illustrates this difficulty by imagining how
one might formulate a sentence that says that under certain conditions a
car will start.  In English we might say, for example: ``If the fuel
tank is not empty and if you turn the ignition key, the car will
start.''  But this simple sentence is not true of a world in which the
carbureutor is broken, or of which the fuel tank (while not empty) is
full of water, or of which the exhaust pipe has a potato stuck in it, or
$ \ldots $.  Indeed, it seems there might be an infinite number of {\it
qualifications⎇ that would need to be stated in order to make such a
sentence true (of the world the designer has in mind---or comes to have
in mind).  Of course, just what it means for a designer to have a world
in mind is problematical; he probably didn't even think of the
possibility of the potato in the tailpipe until it was mentioned by
someone else who happened to conceive of such a world.

Science has the same problem.  Our theories of the physical world are
all falsifiable, and, indeed, we expect scientific progress to falsify
the theories we have and to replace them by others.  When we conclude
something based on a current physical theory, we admit the dependence of
the conclusion on the theory and modify the theory if the conclusion is
contradicted by subsequent facts.  Those who would argue that logical
languages are inadequate for representing knowledge about the world
\cite{McDermott1987⎇ would also seem to have to doubt the utility of any
of the languages that science uses to describe and predict reality.
Merely because our conceptualization of the world at any stage of our
progress toward understanding it may (inevitably will!) prove to be
inaccurate does not mean that this conceptualization is not in the
meantime useful.

If logical languages are to serve us as vehicles for representing the
world, we must use these languages in a way that tolerates our changing
notions of the world.  An example of the need for this sort of
flexibility arises whenever we use non-definitional, universal
statements.  For example, suppose $\Delta$ contains the statement ${\tt
(\forall x)Apple(x) \wedge Ripe(x) \supset Edible(x)⎇$.  (We trust that
the reader understands that the mnenomics we use in our examples must be
backed up by sufficient additional statements in $\Delta$ to insure that
these mnemonics have roughly their intended meanings.)

One can easily think of exceptions to this general rule about the
edibility of apples.  What about ${\tt Wormy(x)⎇$?  Or ${\tt
Rotten(x)⎇$?  These {\it qualifications⎇ might be quite numerous, and not
all of them will be imagined at the time of design.

AI researchers have suggested several approaches to the {\it
qualification problem⎇ and to related problems.  Some of these involve
the invention of new logics (so-called {\it non-monotonic⎇ logics)
\cite{McDermott1980,McDermott1982⎇.  Some involve the use of inference
rules (called {\it default rules⎇) whose applicability to a set of
sentences $\Delta$ depends on what is {\it not⎇ in $\Delta$ as well as
what is \cite{Reiter1980⎇.  Some involve the notion of minimal models
\cite{McCarthy1980⎇.  Some use multiple (more than two) truth values to
represent various degrees of knowledge \cite{Ginsberg1987⎇. All these
approaches have the property that if new information (e.g.  ${\tt
Wormy(Apple1))⎇$ is added to a knowledge base, some of the conclusions
(e.g. ${\tt Edible(Apple1))⎇$ drawn from the earlier version of the
knowledge base will have to be retracted.  For this reason, these
approaches embody what is called {\it non-monotonic reasoning⎇.
(Ordinary logical reasoning is monotonic in the sense that the set of
conclusions that can be drawn from a set of sentences is not diminished
if new sentences are added.) 

We will briefly describe one of these approaches, that based on minimal
models, in order to illustrate what can be done.

Suppose a certain conceptualization of the world is embodied in the
general rule: \[{\tt (\forall x) Q(x) \supset P(x)⎇\] We may know that
the rule is not strictly correct without additional qualifications, but
we may want to use the rule nevertheless to express the fact that
``typically'' all objects satisfying property $Q$ also satisfy property
$P$.  Or we may want to use the rule in a system that can tolerate
qualifications to be added later.

One way to hedge the rule is to introduce the concept of {\it
abnormality⎇, denoted by the relation constant ${\tt Ab⎇$.
\cite{McCarthy1986⎇ Then we can say that all objects that are not
abnormal and that satisfy property $Q$ also satisfy property $P$: \[{\tt
(\forall x) Q(x) \wedge \neg Ab(x) \supset P(x)⎇\] Which objects are
abnormal and which are not (if we know these facts) can be specified by
other sentences in $\Delta$.  For example we may know that the objects
denoted by ${\tt A⎇$ and ${\tt B⎇$ are abnormal: ${\tt Ab(A) \wedge
Ab(B)⎇$.

If we do not know whether or not something, say the object denoted by
${\tt C⎇$, is abnormal, we might be prepared to assume that it is not.
Later, if we learn that it is, we can add ${\tt Ab(C)⎇$ to $\Delta$.

How do we say that something is not abnormal unless it is required to be
by what we have already said in $\Delta$?  One way to do this is to
specify that the intended model lies within a special subset of the
models of $\Delta$.  The subset is characterized by those models having
the smallest possible sets of abnormal objects consistent with what we
know must be abnormal.  These models are called minimal with respect to
${\tt Ab⎇$.  McCarthy \cite{McCarthy1980⎇ has shown how to compute a
sentence $\phi$ such that the models of $\Delta \wedge \phi$ are just
the models in this subset.  The formula $\phi$ is called the {\it
circumscription formula⎇ of ${\tt Ab⎇$ in $\Delta$.

Although the process of computing circumscription for general $\Delta$
in complex ($\phi$ might even be a second-order predicate calculus
formula), there are some interesting special cases.  Many of these have
been investigated by Lifschitz \cite{Lifschitz1985⎇ and are also
described in \cite{Genesereth1987⎇.

\subsection{Change⎇

So far we have focussed our attention on that part of a
conceptualization consisting of world objects, functions, and relations.
But a complete picture of the world must also include a guess about {\it
see⎇ and {\it effect⎇.  The function {\it effect⎇ characterizes how the
world changes.  If an agent is to perform appropriately in the world, it
must be able to anticipate and influence these changes. Although it
sounds unnecessarily tedious, an agent must know that after it moves
from $A$ to $B$, for example, it will be at $B$.  It must also know
that, all other things being equal, other objects will remain where they
were before it moved to $B$.  In summary, an agent must have as part of
its knowledge some idea of how {\it effect⎇ changes the world.

Several approaches have been pursued.  Most work has been done using a
conceptualization that includes objects called {\it states⎇.  States are
imagined as instantaneous snapshots of the world.  Change is
characterized as a transition from one state to another.  Changes may
occur as a result of actions on the part of the machine; we want our
machines to be able to compute what actions they ought to perform in
order that certain desireable states, called {\it goal states⎇, result.
A key problem in characterizing the effects of a given machine action on
world relations involves how to specify the relations that do not
change.  This has been called {\it the frame problem⎇.  

The frame problem has been thoroughly discussed in the literature. (For a
recent collection of articles, including an overview with bibliogaphy, see
\cite{Brown1987⎇.)  In
attempting to deal with the frame problem in their system called STRIPS,
Fikes and Nilsson \cite{Fikes1971⎇ described the effects of a machine's
actions by listing those relations that were changed by the action. They
assumed that those relations not mentioned were not changed.  Hayes
\cite{Hayes1979,Hayes1985⎇ introduced the notion of {\it histories⎇ in
an attempt to define a conceptualization in which the frame problem was
less severe.  McCarthy \cite{McCarthy1986⎇ and Reiter \cite{Reiter1980⎇
proposed nonmonotonic reasoning methods for dealing with the frame
problem.  In the language of circumscription, their approaches assumed
minimal changes consistent with the relations that were known to change.
However, Hanks and McDermott \cite{Hanks1986⎇ showed that a
straightforward application of circumscription does not produce results
strong enough to solve the frame problem.  In response, Lifschitz
\cite{Lifschitz1986⎇ introduced a variant called {\it pointwise
circumscription⎇.  He also proposed a reconceptualization of actions and
their effects that permits the use of ordinary circumscription in
solving the frame problem and the qualification problem
\cite{Lifschitz1987⎇.  Shoham \cite{Shoham1986⎇ proposed an
alternative minimization method related to circumscription, called {\it
chronological ignorance⎇.

Although the frame problem has been extensively studied, it remains a
formidable conceptual obstacle to the development of systems that must
act in a changing world.  As with many of the other problems confronting
AI, the frame problem arises in any of the approaches involving the use
of declarative knowledge.

\subsection{Uncertain Knowledge⎇

When one is uncertain about the world, one cannot specify precisely
which relations hold in the world.  Nevertheless, one might be
able to say that at least one of a set of relations holds.  Logical
disjunctions permit us to express that kind of uncertain knowledge.

As they stand, however, logical representations aren't adequate for
representing other types of uncertain knowledge.  How do we say, for
example, ``It is likely that it will be sunny in Pasadena on New Year's
day''?  We could, of course embed probability information itself in the
sentence, and this approach and others have been followed.  Attempts to
fuzz the crisp true/false semantics of logical languages have led to an
active AI research subspecialty
\cite{Kanal1986,Shortliffe1976,Pearl1986⎇.

The approach followed by \cite{Nilsson1986⎇, for example, is to imagine
that a probability value is associated with each of a set of possible
conceptualizations (interpretations).  The machine designer makes this
assignment implicitly by composing a set of first-order predicate
calculus sentences each having a probability value.  Each of these
values is the sum of the probabilities of those interpretations that are
models of the associated sentence.  In this way the set of sentences
with their probabilities induce constraints on what the probabilities of
the interpretations can be.  These constraints can then be used to
calculate bounds on the probabilities of other sentences about the
world.  Using this approach is computationally quite intractable,
however, and approximate methods for dealing with uncertain knowledge
must be found.

\subsection{Embedded Systems⎇

\begin{verse⎇
{\it Those who will not reason\\
Perish in the act;\\
Those who will not act\\
Perish for that reason.\\
--- W. H. Auden⎇\footnote{we need to find a citation for this⎇
\end{verse⎇

We must not allow our concentration on logic and reasoning to cause us
to forget that our machines are embedded in the world.  The machine
senses the world, through {\it see⎇, and acts on the world, through {\it
act⎇.  Very little research has been done on these connections between
reasoning and the world.  An important problem in this regard is how to
compute which action should be performed under the pressure of time.
Complex reasoning methods might not be able to decide on an action in
the time required.

The need for ``real-time'' response has led to an interesting variety of
machine architectures.  Rosenschein and Kaelbling \cite{Rosenschein1986⎇
have proposed {\it situated automata⎇---finite state machines that do not
reason with explicit sentences but, rather, react virtually instantaneously
to sensory stimuli.  Kaelbling \cite{Kaelbling1987⎇ has proposed hierarchical
systems in which the lower levels are able to compute actions more quickly
(if less intelligently) than the higher ones.  Under time pressure, if
the higher levels have not finished their more elaborate computations, the
lower ones dominate.

Other examples of architectures that do not rely on the lumbering
reasoning apparatus associated with declarative representations can be
found in the adaptive networks of the {\it connectionists⎇
\cite{Rumelhart1986⎇, in the finite-state machines of Brooks
\cite{Brooks1988⎇, and in the PENGI system of Agre and Chapman
\cite{Agre1987⎇.  

Good as they are for computing actions quickly however, networks that
do not reason may sometimes perish in the act.  Connecting perception
to reasoning and reasoning to action remains an important challenge for
all of the approaches to AI.

\section{Conclusions⎇

Logic provides the vocabulary and many of the techniques needed both for
analyzing the processes of representation and reasoning and for
synthesizing machines that represent and reason.  The fact that we
discover elements of reasoning and intelligent behavior that challenge
the techniques of ordinary logic does not necessarily imply that we
ought to abandon the solid base that we have already built.  On the
contrary, it appears that imaginative extensions to ordinary first-order
logic are successfully dealing with many of its purported inadequacies.

Logic itself (originally invented to help formalize human reasoning) has
evolved dramatically in the last 2000 years.  Anyone who attempts to
develop theoretical apparatus relevant to systems that use and
manipulate declaratively represented knowledge, and does so without
taking into account the prior theoretical results of logicians on these
topics, risks (at best) having to repeat some of the work done by the
brightest minds of the twentieth century and (at worst) getting it
wrong!

Of course, it may turn out that we cannot adequately and usefully
represent the knowledge needed by intelligent machines in declarative
sentences.  The declarative thesis is still just a thesis.  If it is
wrong, each application would seem to require a machine whose knowledge
is encoded in procedures specialized to that niche.  Many of these
specialized systems will have similar knowledge---differently (and
seemingly wastefully) re-expressed to match each situation.  There is
good reason to recoil from that prospect.  It's simply too much work!
There are too many niches.  Considering the high payoff and the
impressive results obtained so far, it seems much too early to give up
the grand vision of the logical approach to AI.

\section{Acknowledgments⎇

The author thanks the Palo Alto Laboratory of the Rockwell Scientific
Center for support.  David Kirsh, Carl Hewitt, Devika Subramanian,
and Yoav Shoham provided helpful suggestions.

\begin{thebibliography⎇{999⎇

\bibitem[Agre 1987]{Agre1987⎇
Agre, P., and Chapman, D., ``Pengi: An Implementation of a Theory of
Activity,'' {\it Proceedings of Sixth National Conference on Artificial
Intelligence⎇, pp. 268-272, Morgan Kaufmann, Los Altos, CA, 1987.

\bibitem[Appelt 1985]{Appelt1985⎇
Appelt, D. E., {\it Planning English Sentences⎇, Cambridge University
Press, New York, 1985.

\bibitem[Brown 1987]{Brown1987⎇
Brown, F., {\it The Frame Problem in Artificial Intelligence⎇,
Proceedings of the 1987 Workshop, Morgan Kaufmann, Los Altos, CA, 1987.

\bibitem[Brachman 1985]{Brachman1985⎇
Brachman, R., Gilbert, V., Levesque, H., ``An essential hybrid
reasoning system: knowledge and symbol level accounts of KRYPTON,'' 
{\it Proceedings of the International Joint Conference on Artificial
Intelligence⎇, Los Angeles, Calif., 1985.

\bibitem[Brooks 1988]{Brooks1988⎇
Brooks, R., this volume

\bibitem[Cohen 1987]{Cohen1987⎇
Cohen, P., and Levesque, H., Intention papers

\bibitem[Fikes 1971]{Fikes1971⎇
Fikes, R. E. and Nilsson, N. J., 
``STRIPS: A New Approach to the
Application of Theorem Proving to Problem Solving,''  {\it Artificial
Intelligence⎇, 2(3--4):\ 189--208, 1971.

\bibitem[Genesereth 1984]{Genesereth1984⎇
Genesereth, M. R., ``The Use of Design Descriptions in Automated
Diagnosis,'' {\it Artificial Intelligence⎇, 24(1-3): 411-436, 1984.

\bibitem[Genesereth 1987]{Genesereth1987⎇
Genesereth, M. R., and Nilsson, N. J., {\it Logical Foundations
of Artificial Intelligence⎇, Morgan Kaufmann Publishers, Los Altos
CA, 1987.

\bibitem[Ginsberg 1987]{Ginsberg1987⎇
Ginsberg, M., the multi-valued logic paper.

\bibitem[Grosz 1987]{Grosz1987⎇
Grosz, B. J., et al., ``TEAM: An Experiment in the Design of
Transportable Natural-Language Interfaces,'' {\it Artificial
Intelligence⎇, {\bf 32⎇:2, pp. 173-243, May, 1987.

\bibitem[Hanks 1986]{Hanks1986⎇
Hanks, S. and McDermott, D., ``Default Reasoning, Nonmonotonic Logics,
and the Frame Problem,'' {\it Proceedings of the Fifth National Conference
on Artificial Intelligence⎇, University of Pennsylvania, 1986.
Los Altos, CA: Morgan Kaufmann, 1986.   

\bibitem[Hayes 1979]{Hayes1979⎇
Hayes, P. J., ``The Naive Physics Manifesto,''
in Michie,}D. (ed.), {\it Expert Systems in the Micro-Electronic Age⎇. 
Edinburgh, UK: Edinburgh University Press, 1979, pp.\ 242--270. 

\bibitem[Hayes 1985]{Hayes1985⎇
Hayes, P., ``The Second Naive Physics Manifesto,'' 
in Hobbs,}J.}R. and Moore,}R.}C. (eds.), 
{\it Formal Theories of the Commonsense World⎇. 
Norwood, NJ: Ablex,   1985, pp.\ 1--36.  
(Also in Brachman,}R. and Levesque,}H. (eds.), {\it Readings in
Knowledge Representation⎇.  Los Altos, CA: Morgan Kaufmann, 1985.)

\bibitem[Hayes-Roth 1985]{Hayes-Roth1985⎇
Hayes-Roth, B., ``A Blackboard Architecture for Control,'' {\it
Artificial Intelligence⎇, 26(3):\ 251--321, 1985.  

\bibitem[Hobbs 1985a]{Hobbs1985a⎇
Hobbs, J. R. (ed.),  ``Commonsense Summer: Final Report,'' 
Report}CSLI-85-35.  
Stanford, CA: Stanford University, 
Center for the Study of Language and Information, 1985.

\bibitem[Hobbs 1985b]{Hobbs1985b⎇
Hobbs,}J.}R. and Moore,}R.}C. (eds.), 
{\it Formal Theories of the Commonsense World⎇. 
Norwood, NJ: Ablex,   1985.

\bibitem[Kaelbling 1987]{Kaelbling1987⎇
Kaelbling's paper.

\bibitem[Kanal 1986]{Kanal1986⎇
Kanal,}L.}N. and Lemmer,}J.}F. (eds), 
{\it Uncertainty in Artificial Intelligence⎇.  
New York:\ North-Holland, 1986.

\bibitem[Konolige 1985]{Konolige1985⎇
Konolige, K., ``Belief and Incompleteness,'' 
in Hobbs,}J.}R. and Moore,}R.}C. (eds.), 
{\it Formal Theories of the Commonsense World⎇. 
Norwood, NJ: Ablex,   1985, pp.\ 359--404.

\bibitem[Lenat 1982]{Lenat1982⎇
Lenat, D. B., ``The Nature of Heuristics,'' {\it Artificial
Intelligence⎇, 19(2):\ 189--249, 1982.

\bibitem[Lenat 1983a]{Lenat1983a⎇
Lenat, D. B., ``Theory Formation by Heuristic Search.  The Nature of
Heuristics, II: Background and Examples,'' {\it Artificial
Intelligence⎇, 21(1--2):\ 31--59, 1983.

\bibitem[Lenat 1983b]{Lenat1983b⎇
Lenat, D. B., 
``EURISKO: A Program that Learns New Heuristics and Domain
Concepts.  The Nature of Heuristics, III: Program Design and Results,''
{\it Artificial Intelligence⎇, 21(1--2):\ 61--98, 1983.

\bibitem[Lenat 1988]{Lenat1988⎇
Lenat, D., and Feigenbaum, E., ``On the Thresholds of Knowledge,''

\bibitem[Lifschitz 1985]{Lifschitz1985⎇
Lifschitz, V., ``Computing Circumscription,''
{\it Proceedings of the Ninth International Joint Conference on Artificial 
Intelligence⎇, Los Angeles, CA, 1985. 
Los Altos, CA: Morgan Kaufmann, 1985, pp.\ 121--127.

\bibitem[Lifschitz 1986]{Lifschitz1986⎇
Lifschitz, V., ``Pointwise Circumscription: Preliminary Report,''
{\it Proceedings of the Fifth National Conference on Artificial
Intelligence⎇, University of Pennsylvania, 1986, Vol.}I\@.
Los Altos, CA: Morgan Kaufmann, 1986, pp.\ 406-410.  

\bibitem[Lifschitz 1987]{Lifschitz1987⎇
Lifschitz, V.,  ``Formal Theories of Action,''
{\it Proceedings of IJCAI-87⎇, vol. 2, pp. 966-972, Morgan Kaufmann,
Los Altos, CA:  Morgan Kaufmann, 1987.

\bibitem[McCarthy 1958]{McCarthy1958⎇
McCarthy, J.  1958. Programs with common sense.  {\it Mechanisation of
Thought Processes, Proc. Symp. Nat. Phys. Lab.⎇, vol. I, pp. 77-84.
London: Her Majesty's Stationary Office.  (Also in {\it Semantic
Information Processing⎇,  M. Minsky (ed.), pp.
403-410, The MIT Press, Cambridge, MA, 1968; and
in Brachman,}R. and Levesque,}H. (eds.), {\it Readings in
Knowledge Representation⎇.  Los Altos, CA: Morgan Kaufmann, 1985.)

\bibitem[McCarthy 1980]{McCarthy1980⎇
McCarthy, J. 1980. Circumscription---a form of non-monotonic reasoning.
{\it Artificial Intelligence,⎇ 13(1,2):27-39.
(Also in:
{\it Readings in Artificial Intelligence⎇,
Webber, B. L., and Nilsson, N. J. (eds.), 
Morgan Kaufmann Publishing Co., 1982.)

\bibitem[McCarthy 1986]{McCarthy1986⎇
McCarthy, J., ``Applications of Circumscription to Formalizing
Commonsense Knowledge,'' {\it Artificial Intelligence⎇, 28(1):\ 89--116,
1986.

\bibitem[McCarthy 1987]{McCarthy1987⎇ 
McCarthy, John, ``Mathematical Logic in 
Artificial Intelligence,'' (draft paper), 1987.

\bibitem[McDermott 1980]{McDermott1980⎇
McDermott, D. and Doyle, J., ``Non-Monotonic Logic I,'' 
{\it Artificial Intelligence⎇, 13(1--2):\ 41--72, 1980.

\bibitem[McDermott 1982]{McDermott1982⎇
McDermott, D., ``Non-Monotonic Logic II: Non-Monotonic Modal Theories,''
{\it Journal of the Association for Computing Machinery⎇, 
29(1):\ 33--57, 1982.

\bibitem[McDermott 1987]{McDermott1987⎇
McDermott, D., ``A Critique of Pure Reason,'' {\it Computational Intelligence⎇,
(forthcoming) (with peer commentaries), 1987.

\bibitem[Moore 1985]{Moore1985⎇
Moore, R. C., ``A Formal Theory of Knowledge and Action,'' 
in Hobbs,}J.}R. and Moore,}R.}C. (eds.), 
{\it Formal Theories of the Commonsense World⎇. 
Norwood, NJ: Ablex,   1985.

\bibitem[Nilsson 1986]{Nilsson1986⎇
Nilsson, N. J., ``Probabilistic Logic,'' {\it
Artificial Intelligence⎇, 1986.

\bibitem[Pearl 1986]{Pearl1986⎇
Pearl, J., ``Fusion, Propagation, and Structuring in Belief Networks,''
{\it Artificial Intelligence⎇, 29(3):\ 241--288, 1986.

\bibitem[Pople]{Pople⎇
Pople, H., 

\bibitem[Reiter 1980]{Reiter1980⎇
Reiter, R., ``A Logic for Default Reasoning,'' {\it Artificial
Intelligence⎇, 13(1--2):\ 81--132,  1980.

\bibitem[Rosenschein 1986]{Rosenschein1986⎇
Rosenschein, S. J. and  Kaelbling, L. P.,  
``The Synthesis of Machines with Provably Epistemic Properties,''
in  Halpern, J. F. (ed.), {\it
Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning
about Knowledge⎇.
Los Altos, CA: Morgan Kaufmann,   1986, pp.\ 83--98.

\bibitem[Rumelhart 1986]{Rumelhart1986⎇
Rumelhart, D. E., et al., %McClelland, J. L., and the PDP Research Group, 
{\it Parallel Distributed Processing: Explorations in the Microstructure of
Cognition⎇\@; Vol.}I: {\it Foundations⎇\@, Vol.}II: {\it Psychological and
Biological Models⎇.  
Cambridge, MA: MIT Press,  1986.

\bibitem[Shoham 1986]{Shoham1986⎇
Shoham, Y., ``Chronological Ignorance: Time, Nonmonotonicity and
Necessity,'' {\it Proceedings of the Fifth National Conference on Artificial
Intelligence⎇, University of Pennsylvania, 1986.
Los Altos, CA: Morgan Kaufmann, 1986, pp.\ 389--393.  

\bibitem[Shoham 1987]{Shoham1987⎇
Yoav's arguments for time versus state

\bibitem[Shortliffe 1976]{Shortliffe1976⎇
Shortliffe, E. H., {\it Computer-Based Medical Consultations: MYCIN⎇,
Elsevier, New York, 1976.

\bibitem[Stickel 1982]{Stickel1982⎇
Stickel, M.}E., A nonclausal connection-graph resolution theorem-proving
program.  In {\it Proceedings of AAAI-82 National Conference on
Artificial Intelligence⎇, pages}229--233, AAAI, Pittsburgh,
Pennsylvania, August 1982.  (Also in:
Stickel, M., ``A Nonclausal Connection-Graph Resolution Theorem-Proving
Program,'' SRI AIC Tech Note 268, October 1982.)

\bibitem[Stickel 1984]{Stickel1984⎇
Stickel, M. E., ``A PROLOG Technology Theorem Prover,'' {\it Proc. 1984
International Symposium on Logic Programming⎇, pp. 211-217, IEEE
Computer Society, February, 1984.

\bibitem[Weyhrauch 1980]{Weyhrauch1980⎇
Weyhrauch, R., Prolegomena to a theory of mechanized formal reasoning.
{\it Artificial Intelligence⎇, 13(1 and 2):133--170, 1980.
(Also in:
{\it Readings in Artificial Intelligence⎇,
Webber, B. L., and Nilsson, N. J. (eds.), 
Morgan Kaufmann Publishing Co., 1982.)

\bibitem[Winker 1982]{Winker1982⎇
Winker, S., ``Generation and Verification of Finite Models and
Counterexamples Using an Automated Theorem Prover Answering Two Open
Questions,'' {\it Journal of the Association for Computing Machinery⎇,
29(2):\ 273--284, 1982.

\bibitem[Wos 1984]{Wos1984⎇
Wos, L., et al., % Winker, S., Smith, B., Veroff, R., Henschen, L.  ``A
New Use of an Automated Reasoning Assistant: Open Questions in
Equivalential Calculus and the Study of Infinite Domains,'' {\it
Artificial Intelligence⎇, 22(3):\ 303--356, 1984.

\end{thebibliography⎇

\end{document⎇